#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e3+10;
const int MAXE = 1e6+10;

#define mes(x) memset(x,0,sizeof(x))

int n,m,ban[MAXN][MAXN],low[MAXN],dfn[MAXN],h[MAXN];
int col[MAXN],blo[MAXN],cnt,tot,nod,root,stk[MAXN],top;
bool able[MAXN],fff;

typedef struct{int v,nxt;} edge;

edge e[MAXE];

void link(int x,int y){e[++cnt] = (edge){y,h[x]};h[x] = cnt;}

vector<int>v_DCC[MAXN];

void tarjin(int x){
	dfn[x] = low[x] = ++tot;
	stk[++top] = x;
	if(x == root && !h[x]) {
		nod++;
		v_DCC[nod].push_back(x);
		return;
	}
	for(int i = h[x];i;i = e[i].nxt){
		int y = e[i].v;
		if(!dfn[y]){
			tarjin(y);
			low[x] = min(low[x],low[y]);
			if(dfn[x] <= low[y]){
				nod++;
				int tmp = 0;
				do{
					tmp = stk[top--];
					v_DCC[nod].push_back(tmp);
				}while(tmp != y);
				v_DCC[nod].push_back(x);
			}
		}else low[x] = min(low[x],dfn[y]);
	}
}

bool dfs(int x,int f,int co){
	if(col[x] && col[x] != co) {
		fff = 1;
		return 1;
	}
	if(col[x]) return 0;
	col[x] = co;
	for(int i = h[x];i;i = e[i].nxt){
		int y = e[i].v;
		if(blo[y] == f){
			if(dfs(y,f,3-co)) return 1;
		}
	}
	return 0;
}

int main (){
	while(scanf("%d %d",&n,&m) && n && m){
		mes(ban);mes(low);mes(dfn);mes(h);mes(blo);mes(able);
		for(int i = 1;i <= nod;i++) v_DCC[i].clear();
		cnt = tot = nod = top = 0;
		for(int i = 1;i <= m;i++){
			int x,y; scanf("%d %d",&x,&y);
			ban[x][y] = ban[y][x] = 1;
		}
		for(int i = 1;i <= n;i++)
			for(int j = i+1;j <= n;j++)
				if(!ban[i][j])
					link(i,j),link(j,i);
		for(int i = 1;i <= n;i++) if(!dfn[i]) tarjin(root=i);
		for(int i = 1;i <= nod;i++){
			for(int j = 0;j < (int)v_DCC[i].size();j++){
				blo[v_DCC[i][j]] = i;
				col[v_DCC[i][j]] = 0;
			}
			fff = 0;
			dfs(v_DCC[i][0],i,1);
			if(fff){
				for(int j = 0;j < (int)v_DCC[i].size();j++){
					able[v_DCC[i][j]] = 1;
				}
			}
		}
		int ans = n;
		for(int i = 1;i <= n;i++) if(able[i]) ans --;
		printf("%d\n",ans); 
	}
	return 0;
}
